﻿using System;
using System.Collections.Generic;
using System.Linq;
using Gqq.Arithmetic.Models;

namespace Gqq.Arithmetic.AtrithQuestions
{
    /// <summary>
    /// 背包问题
    /// 对于Y ≤ W，我们将在总重量不超过Y的前提下，
    /// 总价格所能达到的最高值定义为A(Y)。
    /// 本题中W=15。
    /// 1、A(0)=0。总重量不超过0，一件都放不进去，所以最大价值只能是0
    /// 2、A(1)=max(A(0),max(p[j]+A(1-W[j])))【对于所有的w[j]不大于1】的
#pragma warning disable 1570
    /// 3、通用公式A(n)=max(A(n-1),max(p[j]+A(n-w[j])|w[j]<=n))
#pragma warning restore 1570
    /// </summary>
    public class BagQuestion
    {
        public int MaxWeight { get; set; }
        private static readonly List<Cargo> Cargos;

        //被选中的商品
        private readonly Dictionary<int, List<Cargo>> _selectCargos = new Dictionary<int, List<Cargo>>();

        //不同重量的价格
        readonly List<int> _maxPrice = new List<int>();


        static BagQuestion()
        {
            Cargos = new List<Cargo>();
            Cargos.Add(new Cargo { Id = 1, Price = 4, Weight = 12 });
//            Cargos.Add(new Cargo { Id = 2, Price = 2, Weight = 1 });
            Cargos.Add(new Cargo { Id = 3, Price = 10, Weight = 4 });
//            Cargos.Add(new Cargo { Id = 4, Price = 1, Weight = 1 });
            Cargos.Add(new Cargo { Id = 5, Price = 2, Weight = 2 });
//            Cargos.Add(new Cargo { Id = 6, Price = 3, Weight = 2 });
//            Cargos.Add(new Cargo { Id = 7, Price = 2, Weight = 4 });
        }


        public void Run()
        {

            Console.WriteLine(MaxWeight);
            DoResults();

            //对于扩展方法的技术攻克。
            Console.WriteLine("result:");

            PrintResult();

        }

        private void PrintResult()
        {
            for (int i = 0; i < _maxPrice.Count; i++)
            {
                Console.Write("max weight:");
                Console.WriteLine(i);
                Console.Write("real weight:");
                Console.WriteLine(_selectCargos[i].Sum(x => x.Weight));
                Console.Write("max price:");
                Console.WriteLine(_maxPrice[i]);
                Console.Write("cargos:");

                foreach (var cargo in _selectCargos[i])
                {
                    Console.Write(cargo.Id + "  ");
                }
                Console.WriteLine();
                Console.WriteLine();
            }
        }

        private void DoResults()
        {
            int maxWeight = MaxWeight;
            var results = _maxPrice;
            for (int w = 0; w <= maxWeight; w++)
            {
                List<Cargo> selectedCargos = new List<Cargo>();
                if (w == 0)
                {
                    results.Add(0);
                    //如果weight=0，则不加入任何商品
                    _selectCargos.Add(0, selectedCargos);
                }
                else
                {
                    int maxP = results[results.Count - 1];
                    selectedCargos.AddRange(_selectCargos[results.Count - 1]);
                    foreach (Cargo cargo in Cargos)
                    {
                        //最大价格的求法。
                        if (w < cargo.Weight || cargo.Price + results[w - cargo.Weight] <= maxP) continue;
                        selectedCargos.Clear();
                        maxP = cargo.Price + results[w - cargo.Weight];
                        //如果选择的商品发生了改变，需要重新设置已经装入的商品
                        selectedCargos.AddRange(_selectCargos[w - cargo.Weight].ToList());
                        selectedCargos.Add(cargo);
                    }
                    results.Add(maxP);
                    _selectCargos.Add(w, selectedCargos);
                }
            }
        }
    }
}
